package com.liu.algorithm01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6, 7};
        int i = binarySearchBasic(a, 2);
        if (i == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("找到的索引值为：" + i);
        }

        int[] b = {1, 2, 3, 4, 5, 6, 7};
        int i1 = binarySearchBalance(b, 3);
        if (i1 == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("找到的索引值为：" + i1);
        }


        // java中的二分查找
        // -3 = -插入点 - 1
        int[] c = {12, 23, 32, 55};
        int target = 26;
        int i2 = Arrays.binarySearch(c, target);
        System.out.println(i2);
        if (i2 < 0) {
            int insertIndex = Math.abs(i2 + 1);
            int[] d = new int[c.length + 1];
            /*
                src - 源数组。
                srcPos - 源数组中的起始位置。
                dest - 目标数组。
                destPos - 目标数据的起始位置。
                length - 要复制的数组元素个数
             */
            // [0, 0, 0, 0, 0]
            System.arraycopy(c, 0, d, 0, insertIndex);
            System.out.println(Arrays.toString(d));
            d[insertIndex] = target;
            System.arraycopy(c, insertIndex, d, insertIndex + 1, c.length - insertIndex);
            System.out.println(Arrays.toString(d));


        }

        int[] e = {1, 2, 4, 4, 4, 5, 6, 6, 7};
        int i3 = binarySearchLeftmost1(e, 4);
        if (i3 == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("找到的索引值为：" + i3);
        }

        int[] f = {1, 2, 4, 4, 4, 5, 6, 6, 7};
        int i4 = binarySearchRightmost1(f, 4);
        if (i4 == -1) {
            System.out.println("未找到");
        } else {
            System.out.println("找到的索引值为：" + i4);
        }


        int[] g = {1, 2, 4, 4, 4, 8, 8};
        int i5 = binarySearchReturnLeft(g, 4);
        System.out.println("5的索引值为：" + i5);

        int[] h = {1, 2, 4, 4, 4, 7, 7};
        int i6 = binarySearchReturnRight(h, 4);
        System.out.println("5的索引值为：" + i6);

        System.out.println("--------------返回小于4的值---------------------");
        int[] num1 = {1, 2, 4, 4, 4, 7, 8};
        ArrayList<Integer> res1 = binarySearchLeftMost(num1, 4);
        System.out.println(res1);
        System.out.println("--------------返回小于等于4的值---------------------");
        int[] num2 = {1, 2, 4, 4, 4, 7, 8};
        ArrayList<Integer> res2 = binarySearchRightMost(num2, 4);
        System.out.println(res2);
        System.out.println("--------------返回4<=x<=7的值---------------------");
        int[] num3 = {1, 2, 4, 4, 4, 7, 7};
        int lowerIndex = binarySearchLeftMost2(num3, 4);// 2
        int upperIndex = binarySearchLeftMost2(num3, 7);// 5
        System.out.println(upperIndex);
        List<Integer> between4and7 = new ArrayList<>();
        for (int index = lowerIndex; index <= upperIndex; index++) {
            between4and7.add(num3[index]);
        }
        System.out.println("Values between 4 and 7:" + between4and7);

        System.out.println("--------------返回4<x<7的值---------------------");
        List<Integer> between2and7 = new ArrayList<>();
        int[] num4 = {1, 2, 2, 2, 6, 7, 7};
        int lowIndex = binarySearchRightMost2(num4, 2); // 3
        System.out.println(lowIndex);
        int uppIndex = binarySearchLeftMost2(num4, 7); // 5
        System.out.println(uppIndex);
        for (int in = lowIndex + 1; in <= uppIndex - 1; in++) {
            between2and7.add(num4[in]);
        }
        System.out.println("Values between 2 and 7:" + between2and7);
    }

    /**
     * 二分查找基础版
     *
     * @param a      带查找的升序数组
     * @param target 带查找的目标值
     * @return 找到返回索引，找不到返回索引-1
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1; // 设置指针和初值
        int count = 0;
        while (i <= j) { // i ~ j 范围内有值存在
            int m = (i + j) >>> 1; // m为中间索引 // >>> 右移一位等于 除2
            if (a[m] < target) { // 目标值在右边
                i = m + 1;
            } else if (a[m] > target) {  //目标值在左边
                j = m - 1;
            } else {
                System.out.println("循环次数基础版:" + count);
                return m;
            }
            count++;
        }

        return -1;
    }

    /*
        问题1：为什么是 i <= j 意味着区间内有为比较的元素，而不是 i < j?
                i == j 意味着i，j指向的元素也会参加比较
                i < j 只是意味着 m 指向的元素参与比较

        问题2：(i + j) / 2 有没有问题？
     */

    /**
     * 二分查找平衡版
     *
     * @param a      带查找的升序数组
     * @param target 带查找的目标值
     * @return 找到返回索引，
     * 找不到返回索引-1
     */
    public static int binarySearchBalance(int[] a, int target) {
        int count = 0;
        int i = 0, j = a.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
            count++;
        }
        if (a[i] == target) {
            System.out.println("循环次数平衡版:" + count);
            return i;
        } else {
            return -1;
        }
    }

    /**
     * 查找最左侧的一个重复元素
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引，找不到返回索引-1
     */
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 查找最右侧的一个重复元素
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 找到返回索引，找不到返回索引-1
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (target > a[m]) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    /**
     * 返回查找到的左侧的元素
     *
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 >= target 的最靠左索引
     */
    public static int binarySearchReturnLeft(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * @param a      待查找的升序数组
     * @param target 待查找的目标值
     * @return 返回 <= target 的最靠右索引
     */
    public static int binarySearchReturnRight(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }

    /**
     * 查找小于4的值
     *
     * @param a
     * @param target
     * @return 返回一个数组
     */
    public static ArrayList<Integer> binarySearchLeftMost(int[] a, int target) {
        ArrayList<Integer> number = new ArrayList<>();
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        for (int index = 0; index < i; index++) {
            if (a[index] < a[i]) {
                number.add(a[index]);
            }
        }
        return number;
    }

    /**
     * 找出小于等于4的所有值
     *
     * @param a
     * @param target
     * @return 返回一个小于等于4的数组
     */
    public static ArrayList<Integer> binarySearchRightMost(int[] a, int target) {
        ArrayList<Integer> list = new ArrayList<>();
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        for (int index = 0; index <= (i - 1); index++) {
            if (a[index] <= a[i - 1]) {
                list.add(a[index]);
            }
        }
        return list;
    }

    /**
     * 4 <= x <= 7
     * 1 2 2 4 4 4 7 7
     *
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchLeftMost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }
    public static int binarySearchRightMost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }
}
